package 欧几里得算法及其衍生;

/**
 * @author DELL
 */
public class gcdWithEgcd {


    public static void main(String[] args) {
        int num1 = 104;
        int num2 = 40;

        int c = 16;
        int numbers[] = {num1, num2};

        for (int num : egcd1(num1, num2)) {
            System.out.println(num);
        }
        for (int num : egcd2(numbers)) {
            System.out.println(num);
        }

        for (int num : egcd3(num1, num2, gcd(num1, num2))) {
            System.out.println(num);
        }
        //System.out.println(num);
    }

    public static int congruenceEquation(int a, int b, int c) {
        int[] nums = egcd3(a, b, c);
        int x0 = nums[0];
        int y0 = nums[1];

        return x0 % b;
    }

    // 求解 ax+by = c 一般化的不定方程

    /**
     * @param a
     * @param b
     * @param c
     * @return
     */
    public static int[] egcd3(int a, int b, int c) {
        int finalNum[] = new int[2];
        int m = gcd(a, b);
        if (c % m != 0) {
            return null;
        }

        int[] num2 = egcd1(a, b);
        int x0 = num2[0];
        int y0 = num2[1];

        int x = (c / m) * x0;
        int y = (c / m) * y0;

        finalNum[0] = x;
        finalNum[1] = y;

        return finalNum;
    }

    /**
     *
     * @param a
     * @param b
     * @return
     */
    public static int[] egcd1(int a, int b) {

        int[] numbers1 = new int[2];
        if (b == 0) {
            numbers1[0] = 1;
            numbers1[1] = 0;
            return numbers1;
        }

        int[] number2 = egcd1(b, a % b);

        numbers1[0] = number2[1];
        numbers1[1] = number2[0] - a / b * number2[1];

        return numbers1;
    }

    /**
     * 求解 ax+by = m方程组
     * 其中 m = gcd（a，b）
     *
     * ax1+by1 = m .......1
     * 由gcd(a,b) = gcd(b,r)
     * ax1+by1 = （b）x2+（a%b）y2  又因为  a%b = a - a向下取整除b * b
     * （b）x2+（a - a向下取整除b * b）y2  = gcd(b,r)
     * =》 ay2 + b（x2 - （a向下取整除b * b）y2）  .......2
     *
     * 观察1和2 得：
     * X1 = Y2
     * Y1 = （x2 - （a向下取整除b * b）y2）
     * @param numbers
     * @return
     */
    public static int[] egcd2(int[] numbers) {
        int a = numbers[0];
        int b = numbers[1];

        /*
        迭代周期底部
        * */
        if (b == 0) {
            int[] numbers1 = {1, 0};
            return numbers1;
        }

        int[] numbers2 = {b, a % b};

        int[] numbers3 = egcd2(numbers2);

        numbers2[0] = numbers3[1];
        numbers2[1] = numbers3[0] - a / b * numbers3[1];

        return numbers2;
    }

    /**
     * 求解A和B的最大公约数
     *
     * 欧几里得定理
     *  gcd(a,b) = gcd(b,r)
     *  r = a%b
     * @param a 除数
     * @param b 余数
     * @return 最大公约数
     */
    public static int gcd(int a, int b) { // 第一个形参：除数，第二个形参：余数r
        if (b == 0) {
            return a;
        }
        // gcd(b, r)
        return gcd(b, a % b);
    }
}


